package br.edu.unifei.tfg.algorithms.fm;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import br.edu.unifei.mestrado.commons.graph.GraphWrapper;
import br.edu.unifei.mestrado.commons.graph.NodeWrapper;
import br.edu.unifei.mestrado.commons.graph.RelationshipWrapper;
import br.edu.unifei.mestrado.commons.partition.AbstractPartition;
import br.edu.unifei.mestrado.db.graph.GraphDB;


/**
 * Implementation of the Fiduccia-Mattheyses partitioning algorithm.
 * 
 * @author Bruno Toffolo 
 */
public class FiducciaMattheyses {
	
	private Map<Long, Integer> gainMap = new HashMap<Long, Integer>();
	
	/** Graph the algorithm will be applied to. */
	private GraphWrapper graph;
	
	/** Total size of the graph. */
	int totalNodesSize;
	
	/** Ratio between partitions to be used as the balance condition. */
	private double ratio;
	
	/**
	 * Constructor.
	 * @param graph Graph the algorithm will be applied to. 
	 */
	public FiducciaMattheyses(GraphDB graph, double ratio) {
		this.graph = graph;
		this.ratio = ratio;
		
		totalNodesSize = 0;
		for (NodeWrapper n : graph.getAllNodes()) {
			totalNodesSize += n.getWeight();
		}
	}
	
	/**
	 * Generates an initial partitioning to the input graph. These partitions will be refined by
	 * the Fiduccia-Mattheyses algorithm regarding the balance condition. 
	 */
	private void setInitialPartitioning() {
		int partialPartitionSize = 0;
		for (NodeWrapper node : graph.getAllNodes()) {
			partialPartitionSize += node.getWeight();
			node.setPartition((partialPartitionSize <= ratio * totalNodesSize) ? AbstractPartition.PART_1 : AbstractPartition.PART_2);
		}
	}
	
	/**
	 * Calculates the initial gains of all the graph nodes.
	 */
	private void calculateInitialGains() {
		
		for (NodeWrapper node : graph.getAllNodes()) {
			int gain = 0;
				
			for (RelationshipWrapper relationship : node.getRelationships()) {
				NodeWrapper neighbor = relationship.getOtherNode(node);
				// If nodes are in the same partition, gain will be decreased.
				// Else, gain will be increased.
				if (neighbor.getPartition() == node.getPartition())
					gain -= relationship.getWeight();
				else
					gain += relationship.getWeight();
			}
				
			gainMap.put(node.getId(), gain);
		}
	}
	
	/**
	 * Gets the cell with the biggest gain that satisfies the balance condition.
	 * @return The best cell to be moved
	 */
	private NodeWrapper selectBestCellToMove(List<NodeWrapper> freeCells) {
		
		List<Gain> gains = new ArrayList<Gain>(freeCells.size());
		for (NodeWrapper node : graph.getAllNodes()){
			if (freeCells.contains(node)){
				gains.add(new Gain(node, gainMap.get(node.getId())));
			}
		}
		// Get highest gain
		Collections.sort(gains);
		int i = 0;
		Gain highestPossible;
		
		while (i < freeCells.size()) {
			highestPossible = gains.get(i);
			NodeWrapper possibleBestSwap = highestPossible.getNode();
			
			if ( freeCells.contains(possibleBestSwap) && verifyBalanceCondition(possibleBestSwap) && 
					! possibleBestSwap.isLocked())
				return possibleBestSwap;
			else
				highestPossible = gains.get(i++);
		}
		
		return null;

	}
	
	/**
	 * Verifies if moving the specified node would keep the balance condition satisfied.
	 * @param node The node to be verified
	 * @return If the balance condition would be kept by moving the node
	 */
	public boolean verifyBalanceCondition(NodeWrapper node) {
		
		// Get biggest cell size and calculate Partition A's size
		int maxCellSize = 0;
		int sizePartitionA = 0;
		
		for (NodeWrapper n : graph.getAllNodes()) {
				int nodeWeight = n.getWeight();			
				if (nodeWeight > maxCellSize)
					maxCellSize = nodeWeight;		
				if (AbstractPartition.PART_1 == n.getPartition())
					sizePartitionA += nodeWeight;
		}
		
		// Verify if balance condition is kept
		if ( (ratio*totalNodesSize - maxCellSize <= sizePartitionA) && (sizePartitionA <= ratio*totalNodesSize + maxCellSize) )
			return true;
		else
			return false;
	}
	
	/**
	 * Updates the gains of the cells that are neighbors to the one being moved.
	 * @param node The cell being moved.
	 */
	public void updateAffectedCellsGain(NodeWrapper node, List<Move> moves) {
		for (RelationshipWrapper relationship : node.getRelationships()) {
			NodeWrapper neighbor = relationship.getOtherNode(node);
			int neighborGain = gainMap.get(neighbor.getId());
			
			int weight = relationship.getWeight();

			// Get neighbor's partition
			int neighborPartition = neighbor.getPartition();
			
			// If neighbor has been previously moved, adjust the partition to the new one
			for (Move move : moves)
				if (move.getNode().getId() == neighbor.getId())
					neighborPartition = (AbstractPartition.PART_1 == neighbor.getPartition()) ? AbstractPartition.PART_2 : AbstractPartition.PART_1;
			
			// Get the new partition of the cell being moved
			int movedCellPartition = (AbstractPartition.PART_1 == node.getPartition()) ? AbstractPartition.PART_2 : AbstractPartition.PART_1;
			
			
			// If cells are now in the same partition, decrease gain as making them separated would increase the cut 
			if (movedCellPartition == neighborPartition) {
				gainMap.put(neighbor.getId(), neighborGain + weight);
			}
			// Otherwise, increase gain as their union would reduce the net cut
			else {
				gainMap.put(neighbor.getId(), neighborGain - weight);
			}
		}
	}
	
	/**
	 * Finds the best sequence of moves (M1, M2, ..., Mk) such that G(k) is maximum. 
	 * @param moves The whole sequence of moves
	 * @return The value of k
	 */
	private int findMaximumPartialGain(List<Move> moves) {
		int partialGain = 0;
		int maxGain = 0;
		int maxMove = 0;
		int i = 0;
		
		for (Move move : moves) {
			++i;
			partialGain += move.getGain();
			if (partialGain > maxGain) {
				maxGain = partialGain;
				maxMove = i;
			}
		}
		
		return (partialGain <= 0) ? -1 : maxMove;
	}
	
	/**
	 * Changes the nodes in the graph with the best sequence of moves found, making the swaps
	 * permanent before going to the next iteration. 
	 * @param moves Sequence of moves to be made permanent
	 */
	private void makeAllMovesPermanent(List<Move> moves) {
		for (Move move : moves) {
			NodeWrapper node = move.getNode();
			if (AbstractPartition.PART_1 == node.getPartition())
				node.setPartition(AbstractPartition.PART_2);
			else if (AbstractPartition.PART_2 == node.getPartition())
				node.setPartition(AbstractPartition.PART_1);
			else
				throw new IllegalArgumentException("Invalid move");
		}
	}
	
	/**
	 * Execute the Fiduccia-Mattheyses algorithm.
	 */
	public void run() {
		
		// Brauer's steps 1, 2 and 3 are not necessary as we are not using hypergraphs
		
		
		// Flag to determine if the partitioning is finished
		boolean stop = false;
		
		// Create a list of the cells that are not locked.
		List<NodeWrapper> freeCells;
		
		// Create a list to store the partial moves.
		List<Move> moves = new ArrayList<Move>();
		
		// Brauer's Step 4
		// Initially divide the graph into two partitions to be refined later.
		setInitialPartitioning();
		
		// Create a list of all the cells in the graph
		List<NodeWrapper> allCells = new ArrayList<NodeWrapper>();
		for (NodeWrapper node : graph.getAllNodes()){
			allCells.add(node);
		}
		// Begin FM algorithm
		do {
			
			moves.clear();
			
			// Brauer's Step 5
			// Calculate the initial gains of the nodes.
			calculateInitialGains();
			
			freeCells = new ArrayList<NodeWrapper>(allCells);
			for (NodeWrapper cell : freeCells)
				cell.unlock();
			
//			System.out.println("=== Free cells = " + freeCells.size());
//			for (Node cell : graph.getAllNodes())
//				if (!cell.equals(graph.getReferenceNode()))
//					System.out.println("ID = " + cell.getId() + "\tPartition = " + cell.getProperty(GraphProperties.PARTITION) + "\tGain = " + cell.getProperty(GraphProperties.GAIN));
			
			do {
				// Brauer's Step 6
				NodeWrapper bestCell = selectBestCellToMove(freeCells);
				if (bestCell == null) {
					stop = true;
					freeCells.clear();
				}
				else {
					// Brauer's Step 7
					bestCell.lock();			
					moves.add(new Move(bestCell, gainMap.get(bestCell.getId())));
					freeCells.remove(bestCell);
					
					// Brauer's Step 8
					updateAffectedCellsGain(bestCell, moves);
					
//					System.out.println("=== Free cells = " + freeCells.size());
//					for (Node cell : graph.getAllNodes())
//						if (!cell.equals(graph.getReferenceNode()))
//							System.out.println("ID = " + cell.getId() + "\tPartition = " + cell.getProperty(GraphProperties.PARTITION) + "\tGain = " + cell.getProperty(GraphProperties.GAIN));
//					
//					System.out.println("\n\n");
				}
				
			// Brauer's Step 9
			}  while(!freeCells.isEmpty());
			
			// Brauer's Step 10
			int i = findMaximumPartialGain(moves);
//			System.out.println("\n===\nmaximum partial gain = " + i + "\n\n\n");
			if (i < 0) {
				stop = true;
				break;
			}
			else
				// Brauer's Step 11
				makeAllMovesPermanent(moves.subList(0, i));
			
		// Brauer's Step 12
		} while (stop == false);
		
		for (NodeWrapper node : graph.getAllNodes()){
			node.unlock();
		}
		gainMap.clear();
	}

}